The term “link” is often used to refer to the connection between two devices on a computer network. The link may be a physical medium, such as a copper wire, a coaxial cable, any of a host of different fiber optic lines or a wireless connection. In addition, network devices may define “virtual” or “logical” links, and map the virtual links to the physical links. As networks grow in size and complexity, the traffic on any given link may approach a maximum bandwidth capacity for the link, thereby leading to congestion and loss.
Multi-protocol Label Switching (MPLS) is a mechanism used to engineer traffic patterns within Internet Protocol (IP) networks. Traffic engineering may be applied within a network for a variety of purposes, such as to route traffic around network failures or congested links or to direct certain traffic along a particular path through the network that meets a set of explicit quality of service (QoS) requirements. For example, a router within the network may establish a label switched path (LSP) in a MPLS/IP network using a resource reservation protocol, such as the Resource Reservation Protocol with Traffic Engineering extensions (RSVP-TE). Once a packet is mapped on to an LSP by a head-end label edge router (LER) for the LSP and forwarded by the LER, the intermediate devices along the LSP forward the packet based on labels attached to the packet, rather than making independent forwarding decisions based on the packet destination and the intermediate devices' routing information. A Traffic Engineering LSP (TE LSP) may in this way be used to define and implement a path from a source device to a destination device that satisfies requirements for certain traffic transported by the network.
The explicit requirements that must be satisfied by an LSP represent constraints upon the set of possible paths from the source device to the destination device. These constraints, such as available bandwidth, cause shortest path first algorithms to compute a satisfactory path with regard to the constraint metrics. The network routers then establish an LSP that matches the computed path and, using the LSP, forward traffic in a manner that satisfies the constraints. Constrained shortest path first (CSPF) thus represents a fundamental building block for traffic engineering systems, including MPLS and Generalized MPLS (GMPLS) networks. However, constraint-based path computation in large, multi-domain, multi-region, and/or multi-layer networks is complex and may in some instances require cooperation between elements in different administrative domains that do not exchange sufficient traffic engineering information for computing multi-domain paths.
Network operators may augment the functionality of their networks by introducing one or more path computation elements (PCEs) that allow the network routers to offload path computation. A PCE establishes PCE communication protocol (PCEP) sessions with one or more path computation clients (PCCs) through a network. Path computation clients, such as routers, issue path computation requests to the PCE using their respective PCEP sessions. The PCE applies constraints provided in a path computation request to compute the path of a TE LSP through a path computation domain that satisfies the constraints. The PCE then returns the path to the requesting PCC, effectively augmenting the network path computation functionality.